from typing import List


class Solution:
    """
    方法：使用单调栈解决柱状图中最大矩形面积问题。维护一个存储索引的单调递增栈，当遇到更小高度时，计算矩形面积并更新最大值。
    
    Args:
        heights: List[int] - 表示每个柱子的高度数组
        
    Returns:
        int - 最大矩形面积
        
    Time: O(n) - 每个元素最多被压入和弹出栈一次
    Space: O(n) - 最坏情况下栈的大小为n
    """
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(-1)
        st = [-1]
        ans = 0
        for right, h in enumerate(heights):
            while len(st) > 1 and h < heights[st[-1]]:
                i = st.pop()
                left = st[-1]
                ans = max(ans, heights[i] * (right-left-1))
            st.append(right)
        return ans